/**
 * File name: GraphUtil.java Author: Willard Wang Create date: Jun 30, 2013
 */
package edu.sjtu.se.prophet.utils;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import org.apache.log4j.Logger;

import edu.sjtu.se.prophet.cluster.Cluster;
import edu.sjtu.se.prophet.cluster.Clusterer;
import edu.sjtu.se.prophet.cluster.InvalidClusterNumberException;
import edu.sjtu.se.prophet.cluster.KMedoids;
import edu.sjtu.se.prophet.cluster.MatrixMapDistanceMeter;
import edu.sjtu.se.prophet.cluster.Point;
import edu.sjtu.se.prophet.cluster.PointWithId;
import edu.sjtu.se.prophet.graph.Branch;
import edu.sjtu.se.prophet.graph.Bucket;
import edu.sjtu.se.prophet.graph.Edge;
import edu.sjtu.se.prophet.graph.Graph;
import edu.sjtu.se.prophet.graph.Node;
import edu.sjtu.se.prophet.io.DenpendencyFinderXMLReader;

/**
 * @author deathspeeder
 * 
 */
public class GraphUtil {
    private static Logger logger = Logger.getLogger(GraphUtil.class);

    public static byte[][] distanceByMatrix(List<Node> nodes, List<Edge> edges) {

        int size = nodes.size();
        logger.info("Debug: size: " + size);
        byte[][] matrix = new byte[size][];

        // set all distance between different nodes to MAX_VALUE
        for (int i = 0; i < size; i++) {
            matrix[i] = new byte[size];
            for (int j = 0; j < size; j++) {
                if (i != j)
                    matrix[i][j] = Byte.MAX_VALUE;
                else
                    matrix[i][j] = 0;
            }
        }

        Map<Node, Integer> indexMap = new HashMap<Node, Integer>();
        for (int i = 0; i < size; i++) {
            indexMap.put(nodes.get(i), i);
        }

        for (Edge edge : edges) {
            int i = indexMap.get(edge.getStart());
            int j = indexMap.get(edge.getEnd());
            matrix[i][j] = 1;
            matrix[j][i] = 1;
        }

        if (size > 3) {
            boolean updated = true;
            for (int it = 2; updated; it++) {
                //if (it > 4)
                //    break;// TODO remove this debug
                updated = false;
                logger.info("Matrix iteration " + (it - 1));
                for (int i = 0; i < size; i++) {
                    for (int j = 0; j < size; j++) {
                        if (matrix[i][j] == it - 1) {
                            for (int k = 0; k < size; k++) {
                                if (k != i && matrix[j][k] == 1
                                        && matrix[i][k] > it) {
                                    matrix[i][k] = (byte) it;
                                    matrix[k][i] = (byte) it;
                                    updated = true;
                                }
                            }
                        }
                    }
                }
            }
        }

        return matrix;
    }

    public static byte[][] distanceByDijkstra(List<Node> nodes, List<Edge> edges) {
        int size = nodes.size();
        logger.info("Debug: size: " + size);
        byte[][] matrix = new byte[size][];

        // set all distance between different nodes to MAX_VALUE
        for (int i = 0; i < size; i++) {
            matrix[i] = new byte[size];
            for (int j = 0; j < size; j++) {
                if (i != j)
                    matrix[i][j] = Byte.MAX_VALUE;
                else
                    matrix[i][j] = 0;
            }
        }

        Map<Node, Integer> indexMap = new HashMap<Node, Integer>();
        for (int i = 0; i < size; i++) {
            indexMap.put(nodes.get(i), i);
        }

        for (int i = 0; i < size; i++) {
            logger.info("Dijkstra iteration " + i);
            Node source = nodes.get(i);
            Set<Node> copyNodes = new HashSet<Node>(nodes.subList(i, size));
            while (!copyNodes.isEmpty()) {
                Node nearestNode = null;
                byte nearestDistance = Byte.MAX_VALUE;
                for (Node node : copyNodes) {
                    if (matrix[indexMap.get(source)][indexMap.get(node)] < nearestDistance) {
                        nearestDistance = matrix[indexMap.get(source)][indexMap
                                .get(node)];
                        nearestNode = node;
                    }
                }

                // all remaining vertices are inaccessible from source
                if (nearestNode == null) {
                    break;
                }

                copyNodes.remove(nearestNode);

                Set<Node> neighbors = new HashSet<Node>();
                neighbors.addAll(nearestNode.getInNodes());
                neighbors.addAll(nearestNode.getOutNodes());
                for (Node neighbor : neighbors) {
                    // TODO this is an unknown bug which reports
                    // NullPointerException when accessing indexMap using a
                    // neighbor. It might be the inconsistency of the graph.
                    if (!indexMap.containsKey(neighbor))
                        continue;
                    byte alter = (byte) (nearestDistance + 1);
                    if (alter < matrix[indexMap.get(source)][indexMap
                            .get(neighbor)]) {
                        matrix[indexMap.get(source)][indexMap.get(neighbor)] = alter;
                        matrix[indexMap.get(neighbor)][indexMap.get(source)] = alter;
                    }
                }
            }
        }

        return matrix;
    }

    public static List<Bucket> generateSubTrees(Graph graph) {
        List<Bucket> result = new ArrayList<Bucket>();

        if (graph.getNodes().size() == 0)
            return result;

        List<Node> nodes = new ArrayList<Node>(graph.getNodes());
        byte[][] distance = GraphUtil.distanceByMatrix(nodes,
                new ArrayList<Edge>(graph.getEdges()));
        List<Point> points = new ArrayList<Point>();
        for (int i = 0; i < nodes.size(); i++)
            points.add(new PointWithId(nodes.get(i).getId()));

        MatrixMapDistanceMeter meter = new MatrixMapDistanceMeter(
                points.toArray(new PointWithId[0]), distance);
        Clusterer clusterer = new KMedoids();

        Collection<Cluster> clusters = null;
        try {
            clusters = clusterer.cluster(points, meter,
                    getNumberOfClasses(graph));
        } catch (InvalidClusterNumberException e) {
            logger.error("Cluster number " + getNumberOfClasses(graph), e);
        }

        logger.info("Clusters generated successfully");

        for (Cluster c : clusters) {
            Bucket bucket = new Bucket();
            for (Point p : c.getPoints()) {
                PointWithId point = (PointWithId) p;
                bucket.addAtFront(graph.findNode(point.getId()));
            }
            result.add(bucket);
            logger.debug("Bucket size: " + bucket.getData().size());
        }

        return result;
    }

    private static int getNumberOfClasses(Graph graph) {
        Set<String> nameSet = new HashSet<String>();
        for (Node node : graph.getNodes()) {
            if (node.getMetrics().containsKey("File")) {
                String fileName = (String) node.getMetrics().get("File");
                nameSet.add(fileName);
            }
        }
        return nameSet.size();
    }

    public static List<Bucket> generateClasses(Graph graph) {
        Map<String, Bucket> classToMethods = new HashMap<String, Bucket>();
        for (Node node : graph.getNodes()) {
            if (node.getMetrics().containsKey("File")) {
                String fileName = (String) node.getMetrics().get("File");
                if (!classToMethods.containsKey(fileName))
                    classToMethods.put(fileName, new Bucket());
                classToMethods.get(fileName).addAtFront(node);
            }
        }
        return new ArrayList<Bucket>(classToMethods.values());
    }

    public static List<Branch> generateBranch(Graph graph) {
        List<Branch> branches = new ArrayList<Branch>();
        for (int i = 1;; i++) {
            List<Branch> b = generateBranchArDepth(graph, i);
            if (b.size() == 0)
                break;
            branches.addAll(b);
        }
        return branches;
    }

    public static List<Pair<Float, String>> generateDenseBranches(Graph graph) {
        List<Pair<Float, String>> list = new ArrayList<Pair<Float, String>>();
        for (int i = 1;; i++) {
            List<Pair<Float, String>> l = generateDenseBranchAtDepth(graph, i);
            if (l.size() == 0)
                break;
            list.addAll(l);
        }
        // list.addAll(generateDenseBranchAtDepth(graph, 1));

        Collections.sort(list, new Comparator<Pair<Float, String>>() {

            @Override
            public int compare(Pair<Float, String> o1, Pair<Float, String> o2) {
                if (o1.getLeft() < o2.getLeft())
                    return 1;
                else if (o1.getLeft() > o2.getLeft())
                    return -1;
                else
                    return 0;
            }
        });
        return list;
    }

    /**
     * @param graph
     * @param i
     * @return
     */
    private static List<Branch> generateBranchArDepth(Graph graph, int depth) {
        List<Branch> branches = new ArrayList<Branch>();
        for (Node node : graph.getNodes()) {
            branches.addAll(generateBranchAtDepth(node, depth));
        }
        return branches;
    }

    /**
     * @param graph
     * @param i
     * @return
     */
    private static List<Pair<Float, String>> generateDenseBranchAtDepth(
            Graph graph, int depth) {
        List<Pair<Float, String>> list = new ArrayList<Pair<Float, String>>();
        for (Node node : graph.getNodes()) {
            list.addAll(generateDenseBranchAtDepth(node, depth));
        }
        return list;
    }

    /**
     * @param node
     * @param depth
     * @return
     */
    private static List<Branch> generateBranchAtDepth(Node node, int depth) {
        List<Branch> branches = new ArrayList<Branch>();
        if (depth == 1) {
            branches.add(new Branch(node));
        } else {
            if (node.getOutNodes().size() == 0)
                return branches;
            for (Node out : node.getOutNodes()) {
                List<Branch> outNodeBranches = generateBranchAtDepth(out,
                        depth - 1);
                for (Branch branch : outNodeBranches) {
                    if (!branch.containsNode(node)) {
                        branch.addAtFront(node);
                        branches.add(branch);
                    }
                }
            }
        }
        return branches;
    }

    /**
     * @param node
     * @param depth
     * @return
     */
    private static List<Pair<Float, String>> generateDenseBranchAtDepth(
            Node node, int depth) {
        List<Pair<Float, String>> list = new ArrayList<Pair<Float, String>>();
        if (depth == 1) {
            Pair<Float, String> entry = new Pair<Float, String>(
                    (float) ((Integer) node.getMetrics().get(
                            DenpendencyFinderXMLReader.BUG_COUNT)),
                    node.getId());
            list.add(entry);
            return list;
        } else {
            if (node.getOutNodes().size() == 0)
                return list;
            for (Node out : node.getOutNodes()) {
                List<Pair<Float, String>> outNodeList = generateDenseBranchAtDepth(
                        out, depth - 1);
                for (Pair<Float, String> pair : outNodeList) {
                    String[] ids = pair.getRight().split(";");
                    if (!in(node.getId(), ids)) {
                        // try {
                        float f = (pair.getLeft() * ids.length + (float) ((Integer) node
                                .getMetrics().get(
                                        DenpendencyFinderXMLReader.BUG_COUNT)))
                                / (ids.length + 1);
                        Pair<Float, String> newPair = new Pair<Float, String>(
                                f, node.getId() + ";" + pair.getRight());
                        list.add(newPair);
                        // } catch (NullPointerException e) {
                        // logger.info(pair.getLeft());
                        // logger.info(ids);
                        // logger.info(node.getMetrics());
                        // throw e;
                        // }
                    }
                }
            }
        }
        return list;
    }

    /**
     * @param id
     * @param ids
     * @return
     */
    private static boolean in(String id, String[] ids) {
        for (int i = 0; i < ids.length; i++) {
            if (ids[i].equals(id))
                return true;
        }
        return false;
    }
}
